from aima import * #Problem, Node, depth_first_tree_search, breadth_first_tree_search
import random
from utils import *

def MiM(strategy, visualize):
	pass

class mouse_in_maze_problem(Problem):
	"""The problem of mouse in a maze where a mouse is in the first two cells
	of the third row and there are horizontal and vertical tiles occupying 
	some of the other cells. The initial state is a random distribution of 
	a 3 horizontal and 3 vertical tiles.
	"""
	def __init__(self):
		self.initial = [[None]*6 for i in range(6)]
		#place mouse
		self.initial[2][0] = 'm1'
		self.initial[2][1] = 'm'
		#randomly place horizontal tiles
		horizontal_tiles = 3
		while horizontal_tiles:
			x, y = random.randint(0,5), random.randint(0,4)
			if not (self.initial[x][y] or self.initial[x][y+1]):
				self.initial[x][y] = 'h1'
				self.initial[x][y+1] = 'h'
				horizontal_tiles -= 1
		#randomly place vertical tiles
		vertical_tiles = 3
		while vertical_tiles:
			length, y = random.randint(2,3), random.randint(0,5)
			if length == 2: 
				x = random.randint(0,4)
				if not (self.initial[x][y] or self.initial[x+1][y]):
					self.initial[x][y] = 'v12'
					self.initial[x+1][y] = 'v'
					vertical_tiles -= 1
			else: 
				x = random.randint(0,3)
				if not (self.initial[x][y] or self.initial[x+1][y]):
					self.initial[x][y] = 'v13'
					self.initial[x+1][y] = self.initial[x+2][y] = 'v'
					vertical_tiles -= 1

	def actions(self, state):
		def add_possible_actions(state,pos_actions,x,y):
			if state[x][y] == 'm1':
				#Since the problem would reach a goal state and terminate if the mouse moves to the right and gets out of the maze,
				#then as long as the mouse is in the maze and there is no tile in the cell to it's right, it can always move right
				if y+2 >= len(state[x]) or (y+2 < len(state[x]) and not state[x][y+2]):
					#add it to the possible states
					pos_actions.append((x,y,2,'r'))
				#try to move left
				if y > 0 and not state[x][y-1]:
					#add it to the possible states
					pos_actions.append((x,y,2,'l'))
			#check type of tile
			elif state[x][y] == 'h1':
				#try to move right
				if y+2 < len(state[x]) and not state[x][y+2]:
					#add it to the possible states
					pos_actions.append((x,y,2,'r'))
				#try to move left
				if y > 0 and not state[x][y-1]:
					#add it to the possible states
					pos_actions.append((x,y,2,'l'))
			elif state[x][y] == 'v12':
				#try to move down
				if x+2 < len(state) and not state[x+2][y]:
					#add it to the possible states
					pos_actions.append((x,y,2,'d'))
				#try to move up
				if x > 0 and not state[x-1][y]:
					#add it to the possible states
					pos_actions.append((x,y,2,'u'))
			elif state[x][y] == 'v13':
				#try to move down
				if x+3 < len(state) and not state[x+3][y]:
					#add it to the possible states
					pos_actions.append((x,y,3,'d'))
				#try to move up
				if x > 0 and not state[x-1][y]:
					#add it to the possible states
					pos_actions.append((x,y,3,'u'))
		#an array of sets, each set is a 4-tuple (x,y,length,direction)
		# x,y: coordinates of the first cell occupied by the tile
		# length: length of the tile (2 or 3)
		# direction: direction at which the tile can move
		pos_actions = []
		for x,row in enumerate(state):
			for y,cell in enumerate(row):
				if cell == 'v12' or cell == 'v13' or cell == 'h1' or cell == 'm1':
					add_possible_actions(state,pos_actions,x,y)
		return iter(pos_actions)

	def result(self, current_state, action):
		state = copy_2darr(current_state)
		(x,y,length,direction) = action
		if direction == 'r':
			try:state[x][y+2] = state[x][y+1]
			except:pass
			try:state[x][y+1] = state[x][y]
			except:pass
			state[x][y] = None
		elif direction == 'l':
			state[x][y-1] = state[x][y]
			state[x][y] = state[x][y+1]
			state[x][y+1] = None
		elif direction == 'd' and length == 2:
			state[x+2][y] = state[x+1][y]
			state[x+1][y] = state[x][y]
			state[x][y] = None
		elif direction == 'u' and length == 2:
			state[x-1][y] = state[x][y]
			state[x][y] = state[x+1][y]
			state[x+1][y] = None
		elif direction == 'd' and length == 3:
			state[x+3][y] = state[x+2][y]
			state[x+2][y] = state[x+1][y]
			state[x+1][y] = state[x][y]
			state[x][y] = None
		elif direction == 'u' and length == 3:
			state[x-1][y] = state[x][y]
			state[x][y] = state[x+1][y]
			state[x+1][y] = state[x+2][y]
			state[x+2][y] = None
		return state

	def goal_test(self,state):
		for cell in state[2]:
			if cell == 'm1':
				return False
		return True

	def path_cost(self, c, state1, action, state2):
		return c+1


print breadth_first_search(mouse_in_maze_problem())